import java.util.*;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public boolean isSymmetric(TreeNode root) {
        TreeNode curRoot = createTree(root);
        reverse(root);


        return isSameTree(root, curRoot);

    }

    private TreeNode createTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode treeNode = new TreeNode(root.val);
        if (root.left != null) {
            treeNode.left = createTree(root.left);
        }
        if (root.right != null) {
            treeNode.right = createTree(root.right);
        }
        return treeNode;
    }

    public boolean isSameTree(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return true;
        }
        if (t1 == null || t2 == null) {
            return false;
        }
        if (t1.val != t2.val) {
            return false;
        }
        return isSameTree(t1.left, t2.left) && isSameTree(t1.right, t2.right);
    }

    public TreeNode reverse(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = reverse(root.left);
        TreeNode right = reverse(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

    public int majorityElement(int[] arr) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
        }
        int max = Collections.max(map.values());
        //
//        Set<Integer> integers = map.keySet();
//        for (Integer integer : integers) {
//            if(max==map.get(integer)) {
//                return integer;
//            }
//        }
        //
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        Iterator<Map.Entry<Integer,Integer>> iterator=entries.iterator();
        while(iterator.hasNext()) {
            Map.Entry<Integer, Integer> next = iterator.next();

            if(max==map.get(next.getKey())){
                return next.getKey();
            }
        }
        return -1;


    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        System.out.println(solution.majorityElement(arr));


    }

//    public static void main(String[] args) {
//        TreeNode treeNode1 = new TreeNode(1);
//        TreeNode treeNode2 = new TreeNode(2);
//        TreeNode treeNode3 = new TreeNode(2);
//        treeNode1.left=treeNode2;
//        treeNode1.right=treeNode3;
//        Solution solution = new Solution();
//        System.out.println(solution.isSymmetric(treeNode1));
//    }
}